package pers.qianyu.month_202102.date_20210214;

import java.util.*;

/**
 * 752. 打开转盘锁
 * https://leetcode-cn.com/problems/open-the-lock/
 * - 双向 DFS
 *
 * @author mizzle rain
 * @date 2021-02-14 21:54
 */
public class OpenLock2 {
    public int openLock(String[] deadends, String target) {
        HashSet<String> s1 = new HashSet<>();
        HashSet<String> s2 = new HashSet<>();
        HashSet<String> visited = new HashSet<>(Arrays.asList(deadends));
        int step = 0;
        s1.add("0000");
        s2.add(target);
        while (!s1.isEmpty() && !s2.isEmpty()) {
            HashSet<String> temp = new HashSet<>();
            for (String x : s1) {
                if (visited.contains(x)) continue;
                if (s2.contains(x)) return step;
                visited.add(x);

                for (int i = 0; i < 4; i++) {
                    temp.add(add(x, i, 1));
                    temp.add(add(x, i, -1));
                }
            }
            step++;
            s1 = s2;
            s2 = temp;
        }
        return -1;
    }

    private String add(String str, int pos, int num) {
        char[] arr = str.toCharArray();
        if (arr[pos] == '0') {
            arr[pos] = num > 0 ? '1' : '9';
        } else if (arr[pos] == '9') {
            arr[pos] = num > 0 ? '0' : '8';
        } else {
            arr[pos] += num;
        }
        return new String(arr);
    }
}
